package own.stu.jobgib.playown.alg.leetcode.editor.cn;

//给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 
//
// 你可以假设除了数字 0 之外，这两个数字都不会以零开头。 
//
// 
//
// 进阶： 
//
// 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。 
//
// 
//
// 示例： 
//
// 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 8 -> 0 -> 7
// 
// Related Topics 链表 
// 👍 356 👎 0


import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class AddTwoNumbersIi{
    public static void main(String[] args) {
        Solution solution = new AddTwoNumbersIi().new Solution();
        solution.addTwoNumbers(new ListNode(5), new ListNode(5));
        
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }

        if(l2 == null){
            return l1;
        }

        int len1 = length(l1);
        int len2 = length(l2);
        if(len1 > len2){
            ListNode tmp = l1;
            l1 = l2;
            l2 = tmp;
        }
        // len(l2) >= len(l1)
        int diff = Math.abs(len1 - len2);
        ListNode dummy = new ListNode();
        dummy.next = l2;

        Deque<ListNode> list = new LinkedList<>();
        ListNode cur = dummy;
        list.add(cur);

        while(diff > 0){
            cur = cur.next;
            list.add(cur);
            diff -= 1;
        }

        ListNode p1 = l1;
        ListNode p2 = cur.next;

        while(p1 != null){
            p2.val = p1.val + p2.val;
            cur = cur.next;
            list.add(cur);

            p2 = p2.next;
            p1 = p1.next;
        }

        int carry = 0;
        while(!list.isEmpty()){
            ListNode listNode = list.removeLast();
            int sum = listNode.val + carry;
            listNode.val = sum % 10;
            carry = sum / 10;
        }

        return dummy.val == 0 ? dummy.next : dummy;
    }

    private int length(ListNode node){
        int len = 0;
        while (node != null) {
            node = node.next;
            len += 1;
        }

        return len;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
